1. Field of Invention
The present invention relates to an apparatus and method for scheduling requests to a source device. More particularly, the present invention relates to an apparatus and method for scheduling requests to a source device according to requesting history.
2. Description of Related Art
In systems that are built on a single chip it is not uncommon that there are several independent initiators (such as microprocessors, signal processors, etc.) accessing a dynamic random access memory (DRAM) subsystem. The system may require different qualities of service (QOS) to be delivered for each of the initiators. Secondly, the memory ordering model presented to the initiators is important. Ideally, the initiators want to use a memory model that is as strongly ordered as possible. At the same time, the order in which DRAM requests are presented to the DRAM subsystem can have a dramatic effect on DRAM performance. Yet re-ordering of requests for thread QOS or DRAM efficiency reasons can compromise a strongly ordered memory model. What is required is a unified DRAM scheduling mechanism that presents a strongly ordered memory model, gives differential quality of service to different initiators, and keeps DRAM efficiency as high as possible.
The request stream from each different initiator can be described as a thread. If a DRAM scheduler does not re-order requests from the same thread, intra-thread request order is maintained, and the overall DRAM request order is simply an interleaving of the sequential per-thread request streams. Existing systems might order the requests at a different point in the system than where the DRAM efficiency scheduling occurs (if any is done), and/or the systems re-order requests within a processing thread. For example, requests may be carried from the initiators to the DRAM Controller via a standard computer bus. Request order (between threads and within threads) is established at the time of access to the computer bus, and is not allowed to be changed by the DRAM controller. Another example of DRAM scheduler is provided in U.S. Pat. No. 6,578,117 for achieving a high DRAM efficiency and QOS guarantees. In '117, a thread quality of service scheduler keeps and uses thread state to remember thread scheduling history and help it determine which thread should go next. For example, the scheduler might attempt to schedule requests that access the same DRAM page close to each other so as to increase the chance of getting DRAM page hits.
In further application, queues are used to store the requests and each queue is assigned a priority different from others such that requests in high-priority queue are performed first and requests in low-priority cannot be performed until all requests with higher priority are done. The priority-based schedule is widely used because more important requests are dealt first and performance could be better than normal scheduling method.
However, the priority-based schedule still has some drawbacks. One of the drawbacks is that the low-priority requests might block the high-priority requests. As many initiators submit requests randomly, all the high-priority quests might be finished and therefore the low-priority quests start to be performed. However, once a new high-priority request arrived when performing the low-priority quest, the high-priority request must wait until the low-priority request finishes. In such a condition, the high-priority request is delayed and performance is reduced.